Point cloud data is sampled data representing some feature, object, or element in a multi-dimensional space. A point cloud is usually a very large point set of point cloud data represented in two-dimensional or three-dimensional space, or two and a half dimensional (2.5D) space. The position of each point in the point cloud is defined by a set of coordinates and each point may be assigned an attribute value such as, for example, an intensity value. An iso-line is a line or curve, through a set of data points, made up of points each representing a same attribute value. For example, an iso-line may be generated through a two-dimensional point cloud representing an elevation attribute, where the iso-line is a contour line representing a fixed elevation (e.g., one-hundred (100) meters). Various methods have been used to generate or identify iso-lines through a set of data.
Iso-lines can be generated as derived products from digital elevation model (DEM) data, triangulated irregular network (TIN) data or, less commonly, from point cloud data. A DEM represents elevation in the form of a regular grid or raster (e.g., see https://en.wikipedia.org/wiki/Digital_elevation_model), and a TIN represents elevation in the form of irregularly shaped triangles forming a mesh (e.g., see https://en.wikipedia.org/wikifTriangulated_irregular_network). Digital elevation models conveniently lend themselves to the popular “Marching Squares” approach of generating contour lines, due to the inherent raster representation. The Marching Squares approach requires rasterized data (e.g., see https://en.wikipedia.org/wiki/Marching_squares). Non-uniform data cannot be rasterized without losing accuracy and/or yielding empty or interpolated grid cells. The Marching Squares approach also requires significant run time main memory for the raster.
Performing the Marching Squares approach using smaller partitions requires less memory, however, at the significant expense of efficiency. Triangulated irregular networks allow direct generation of line string segments, from individual triangles, based on linear interpolation between two pairs of three corner vertices (if any of the three vertices are on opposing sides of the respective contour elevation). A DEM can be logically derived from a point cloud based on rasterization, but may yield “empty” raster cells or require some form of interpolation to fill the cells. Also, with point clouds having non-uniform density, detail is sacrificed in some areas and holes or estimates are formed in other areas. Therefore, there is a tradeoff in the configurable grid density when using a rasterization methodology.